\documentclass[a4paper,10pt]{article}
\usepackage[francais]{babel}
\usepackage{ucs}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{graphicx}

\begin{document}

\author{Arnaud Marinho (amarinho@) \\ Clément Lecigne (clecigne@)}
\title{asciIRt} 
\maketitle

\newpage

\begin{abstract}
Ce document décrit avec soin le travail accompli pour la réalisation du programme de
transformation d'images PNM en ascii. Il commence par un tour rapide du programme pour
ensuite s'attarder sur l'algorithme choisi et finir par une explication des différents
tests qui ont été réalisés pour prouver la robustesse et le bon fonctionnement de
notre programme.
\end{abstract}

\newpage

\tableofcontents

\newpage

\section{Introduction}

Cette année, notre premier projet de programmation consiste à écrire un programme dans
le langage C qui transforme des images au format PNM\footnote{Des immenses tableaux de 
pixels.} au format texte (ascii). Ce document explique la démarche accomplise pour
arriver jusqu'à un programme fonctionnel...

\section{La licence}

Les sources de notre programme sont publiées sous la licence BSD\footnote{Berkeley Software Distribution} puisque c'est une licence libre qui est bien adaptée au petit projet universitaire, elle est utilisée par les systèmes d'exploitations BSD libres tels que FreeBSD, OpenBSD et a été rédigée dans la célèbre université de Berkeley (Californie). Elle est moins restrictive que la licence GPL tout en restant compatible avec cette dernière. C'est notamment grâce à elle que l'on dispose d'une pile TCP/IP fiable dans des OS\footnote{Operating System} propriétaires...

\section{Vue générale du programme}

La conception générale du programme n'a pas posé de problème majeur dans le sens ou
le nombre de chemins différents à emprunter est très faible. Nous avons donc opté
pour le schéma suivant:

\begin{enumerate}
\item ouverture du fichier image passé en argument ou dans un pipe
\item lecture de l'entête (type, taille, nombre de couleurs)
\item lecture du fichiers deux lignes par deux lignes
\item conversion des 4 pixels en fonction de notre table ascii (choix d'un algorithme)
\item retourner en 1 pour le fichier image suivant\\
\end{enumerate}

Nous remarquons que les étapes 3 et 4 sont les plus importantes et ceux sont ces dernières
qui différenciront notre programme des autres. 
L'étape 3 joue sur la consomation mémoire de notre 
programme tandis que la quatrième joue sur l'efficacité de notre programme (temps de
conversion et résultat final). Ces deux étapes sont décrites dans les deux sous-sections
suivantes:

\subsection{Gestion de la mémoire}

Nous avons décider de lire notre fichier deux lignes par deux lignes pour limiter la
consomation mémoire (une seule allocation). Pour cela, nous lisons l'entête de l'image
qui contient la longeur et la largeur de l'image, ensuite nous allouons un bloc de mémoire
d'entier (signed int) égale à deux fois la largeur de l'image. Ce bloc va recevoir petit
à petit tous les pixels de l'image avant d'être libéré à la fin du traitement de l'image.
Un autre bloc de mémoire est alloué pour garder en mémoire les caractèristiques de l'image
(struct pnmimg) tout le long du traitement. Plus d'informations sur l'utilisation de
la mémoire sont données dans la section qui parle de valgrind (section \ref{valgrind}).\\

Concernant le stockage de la table de correspondances, nous avons créé une variable globale
qui est un tableau de structures donc chaque structure contient les informations pour un
caractère. Nous aurions très bien pu lire dynamiquement la table dans un fichier externe mais
ceci ne nous a pas semblé utile dans le sens ou on perd en performance et que théoriquement
la table ne doit pas changer. Néanmoins nous avons créé un script en perl qui va lire
la table dans un fichier externe et qui recréé le fichier ascii\_table.h avec notre tableau
de structures. Le script en question se trouve dans le répertoire scripts. L'utilisation
d'une variable globale nous semble judicieuse dans ce cas dans le sens ou le tableau
est réorganisé (cf algo) au début du programme et qu'il est ensuite lu par différentes
fonctions, ainsi nous ne devons pas à chaque coup passer un pointeur sur se tableau ainsi que
sa taille à chaque fois que nous en avons besoins dans une fonction... 
Cependant nous avons fait attention à ce que cela nuise pas à la lecture du
code et nous avons limités la portée de ce tableau à un unique fichier (ascii.c). 
De plus la fonction qui réorganise le tableau a été notée explicitement comme étant non
thread-safe même si nous n'utilisons pas de thread dans notre programme 
(réutilisation de code, modularité, ...).\\

\subsection{Fonctionnement détaillée}

\begin{figure}
\includegraphics[scale=0.6,angle=90]{cg}
\caption{Graphe d'appels *très* simplifié}
\label{callgraph}
\end{figure}

Le graphe figure \ref{callgraph} représente de façon très simplifié l'acheminement des
appels au seins de notre programme lorsqu'on lui fournit une ou plusieurs images.\\

\begin{itemize}
\item la fonction \textit{main()} lance la fonction \textit{piscii\_init()}, s'occupe d'analyser les arguments de la ligne de commande et appelle la fonction \textit{pnmascii()} pour chaque image (passage par flux) trouvée.\\
\item la fonction \textit{piscii\_init()} s'occupe de réorganiser notre tableau de structures global (cf. algorithme).\\
\item la fonction \textit{pnmascii()} lance d'abord la fonction \textit{pnmload()} puis dans
une boucle, elle appelle les fonctions \textit{pnm\_fetchpix} et \textit{pnm\_transpix}.\\
\item la fonction \textit{pnmload()} teste la validité de l'image et renvoie une structure qui décrit l'image (taille, type, nombre de couleurs, ...)\\
\item la fonction \textit{pnm\_fetchpix()} récupère renvoie 2 lignes de pixels convertis en niveau de gris.\\
\item la fonction \textit{pnm\_transpix()} affiche sur la sortie demandée le caractère le plus proche des 4 pixels passés en paramètre.\\
\end{itemize}

\subsection{L'algorithme dans tous ces états}

L'algorithme est la partie la plus critique du programme et c'est sûr cette partie que
nous nous sommes attardées sérieusement. En effet, c'est ce dernier qui détermine la
qualité de notre programme... la vitesse d'exécution, le rendu final...\\


Cette sous partie décrit toutes les étapes effecutées ainsi que les algorithmes intermédiaires
que nous avons effectués pour arriver à notre résultat final, c'est à dire un algorithme qui
répond aux critères suivants.\\

\begin{itemize}
\item performant (temps, consomation mémoire)
\item pas trop difficile
\item facile à modifier
\item qui donne un rendu proche de l'image dans le sujet\\
\end{itemize}

Pour nos tests nous avons utilisés l'image donnée dans le sujet ("la binouse") mais nous avons
également utilisé une image maison qui contient pas mal de couleur que nous pouvons visualiser 
en figure \ref{arc}.

\begin{figure}
\includegraphics[scale=0.8]{foobar}
\caption{Foobar dude !}
\label{arc}
\end{figure}

\subsubsection{Recherche d'informations}

Nous avons commencé par nous documenter sur les différentes techniques de traitement de
l'image (filtrage, compression, ...) mais nous n'avons rien trouvé d'utile pour notre
projet. On a ensuite analyser la table de correspondances qui nous a été fournie avec
le sujet afin de déceler d'éventuelle subtilités telle qu'une bijection mais sur ce point
là nous n'avons, encore une fois, rien trouvé de concluant, la table n'a pas être du choisie
au hasard mais nos compétences en algorithmie ne sont pas encore assez pointues...\\

\subsubsection{Étape 1, la moyenne}

La première idée qui nous ait venu en tête est de faire une bête moyenne sur les 4 pixels que
nous plaçons dans notre tableau de structure. Il suffit ensuite de faire la moyenne de nos
4 pixels pris dans l'image pour trouver celle qui se rapproche le plus dans notre tableau.\\

Cette méthode, très simple, donne un rendu acceptable comme on peut le voir sur la figure \ref{moyenne}
mais n'est pas du tout précise sachant que nous avons des moyennes identiques dans notre tableau
et plusieurs combinaisons de 4 pixels totalement différentes peuvent donner la même moyenne... Nous
avons donc essayer d'améliorer ce premier algorithme.

\begin{figure}
\includegraphics[scale=0.8]{moyenne}
\caption{Un foobar l'algorithme "moyenne"}
\label{moyenne}
\end{figure}

\subsubsection{Étape 2, corrélation de bits}

Nous savons que les pixels sont codés sur un niveau de gris allant de 0 à 255 soit 8 bits. Nous
pouvons donc regrouper nos 4 pixels de 8 bits en un seul int de 32 avec un simple déplacement de
bits comme le montre le schéma figure \ref{algocorr}. Nous avons donc dans un entier non signé
les valeurs des 4 pixels. Il suffit donc de faire l'opération pour les pixels qu'on reçoit pour
les comparer aux valeurs de notre tableau pour trouver ceux qui s'en rapproche le plus et enfin
trouver le bon caractère.\\

\begin{figure}
\includegraphics[scale=0.4]{algocorr}
\caption{Explication de la corrélation de bits}
\label{algocorr}
\end{figure}

Comme on peut le voir sur la figure \ref{corr}, le rendu n'est pas trop mal mais le problème de
cette technique est que nous donnons plus d'importance au pixel qui est le plus à gauche, en 
l'occurence le pixel A dans notre cas. On le voit bien pour les blancs (valeur décimale 255)
qui sont codés avec des J puisque le pixel A pour ce caractère correspond à 255 ce qui n'est
pas vrai pour les pixels B, C et D... Il faut donc trouver une méthode pour palier à ce problème.\\

\begin{figure}
\includegraphics[scale=0.8]{corr}
\caption{Un foobar avec l'algorithme de corrélation de bits}
\label{corr}
\end{figure}

\subsubsection{Étape 3, corrélation de bits triée}

Pour que notre algorithme soit encore plus performant, nous pouvons trier les pixels dans l'ordre
croissant avant de les corréler entre eux. Ainsi nous remplacons la trop forte importance du pixel A
par celui qui a la plus faible valeur pour donner de l'importance aux autres pixels... On se
retrouve avec un foobar qui ressemble à ce qu'on trouve sur la figure \ref{corrtri}.\\

\begin{figure}
\includegraphics[scale=0.8]{sortedcorr}
\caption{Un foobar avec l'algorithme de corrélation de bits triée}
\label{corrtri}
\end{figure}

\subsubsection{Résumé}

Notre fonction \textit{piscii\_init()} s'occupe donc de placer dans notre tableau de structures
le résultat de "la corrélation de bits triée" puis reforme ce dernier pour qu'il soit trié dans
l'ordre croissant en fonction de ce résultat. Ensuite pour transformer 4 pixels en un caractère,
notre fonction \textit{piscii\_trans()} fait le calcul de corrélation de bits triée pour les 4 pixels
passés en paramètre puis recherche par dichotomie dans le tableau de structures la valeur qui
se rapproche le plus de cette dernière pour ensuite retourner le caractère qui correspond
le plus à ces 4 pixels...\\

Cet algorithme permet d'avoir un rendu très proche de l'image convertie qui nous a été donnée
dans le sujet du TP notamment au niveau du bas de l'image ("cul de bouteille") qui n'était point
distinguable avec les algorithmes précédents.

\section{Les tests "alakon"}

Pour tester la robustesse de notre programme, nous devons le tester en lui fournissant des
images semi-valides... assez invalide pour que notre programme plante mais assez valide
pour que notre programme tente de les interpréter. Les sous-sections suivantes résument
les tests qui ont été accompli. Les images sont disponnibles dans le dossier tests de
l'archive du programme.

\subsection{Commentaire}

Une image pnm peut posséder des commentaires dans son entête qui commencent forcement
par un dièse. On peut créer ainsi un fichier pnm avec pleins de commentaires en début
du programme ainsi qu'une image brut avec le caractère '\#' dans son contenu pour
vérifier qu'il n'est pas interpreté comme un commentaire par notre programme.

\begin{footnotesize}
\begin{verbatim}
(clem1@clem1:~/perso/svn/pnmascii)$ ./asciirt tests/nude_comm.ppm -o /dev/null
processing image tests/nude_comm.ppm...
\end{verbatim}
\end{footnotesize}

\subsection{Taille énorme}

Un des test évident à faire est de connaitre "à la louche" les limites de notre programme
en lui passant des images de taille énorme. Comme nous allouons un bloc de mémoire pour
lire 2 ligne à la fois et non pas l'image entière, nous pouvons en déduire que nous pouvons
sans problème passer des images ppm de tailles énormes à notre programme.

\begin{footnotesize}
\begin{verbatim}
(clem1@clem1:~/perso/svn/pnmascii)$ ls -alh tests/bibig.ppm 
-rw-r--r-- 1 clem1 clem1 19M 2007-11-29 17:22 tests/bibig.ppm
(clem1@clem1:~/perso/svn/pnmascii)$ ./asciirt tests/bibig.ppm -o /dev/null
processing image tests/bibig.ppm...
(clem1@clem1:~/perso/svn/pnmascii)$
\end{verbatim}
\end{footnotesize}

\subsection{Entête invalide}

Les images ppm démarrent avec un champs magique commençant par P puis un numéro qui indique
le type d'image. On peut s'amuser à forger des entêtes avec des types invalides pour
voir le comportement du programme.

\begin{footnotesize}
\begin{verbatim}
(clem1@clem1:~/perso/svn/pnmascii)$ ./asciirt tests/nude_fakeheader.ppm -o /dev/null
processing image tests/nude_fakeheader.ppm...
not a valid pnm image
error while loading image.
\end{verbatim}
\end{footnotesize}

\subsection{Taille invalide}

D'un point de vue sécurité, la manipulation de fichier image pause généralement beaucoup
de problème. En effet il suffit de voir le nombre de vulnérabilités trouvées dans les
logiciels de traitement d'images (gimp), les navigateurs (ie), les systèmes d'exploitations 
(GDI)... rien qu'en leur fournissant une image avec des champs width et/ou height falsifiés...
Il est intéressant de tester ces cas dans notre programme. Pour cela on crée de fausses
images avec des entêtes bizaroides...

\begin{footnotesize}
\begin{verbatim}
(clem1@clem1:~/perso/svn/pnmascii)$ ./asciirt tests/nude_fakewidth.ppm -o /dev/null
processing image tests/nude_fakewidth.ppm...
(clem1@clem1:~/perso/svn/pnmascii)$
(clem1@clem1:~/perso/svn/pnmascii)$ ./asciirt tests/nude_fakeheight.ppm -o /dev/null
processing image tests/nude_fakeheight.ppm...
(clem1@clem1:~/perso/svn/pnmascii)$ 
\end{verbatim}
\end{footnotesize}

\subsection{Fuzzage}

En parlant de faille de sécurité, on peut utiliser des programmes nommés fuzzers qui
vont envoyer des multitudes d'images falsifiées à notre programme jusqu'à temps qu'il
produise des anomalies (segfault, consommations mémoire/cpu énormes consommation cpu, ...).
Pour cela nous avons utiliser deux fuzzers opensource nommée zzuf\footnote{zzuf.zoy.org} et
fusil\footnote{fusil.hachoir.org}. Ils fonctionnent de la même manière, on leur passe une
image valide, le chemin de notre programme, des paramètres divers et ils vont modifier
quelques octets dans notre image avant de l'envoyer à notre programme pour voir notre
réaction. Notre programme a survécu à ces deux "monstres" qui ont trouvés à eux deux
pas mal de failles dans des logiciels connus (gimp, clamav, gettext)...


\subsection{Lecture des noms sur l'entrée standard}

Une des fonctionnalités de notre programme doit être de pouvoir lire les chemins des fichiers
images sur l'entrée standard lorsqu'on ne lui pas d'image en argument...

\begin{footnotesize}
\begin{verbatim}
(clem1@clem1:~/perso/svn/pnmascii)$ ls tests/*pbm | ./asciirt -o /dev/null 
processing image tests/p1.pbm...
processing image tests/p4.pbm...
\end{verbatim}
\end{footnotesize}


\section{Valgrindage}
\label{valgrind}

Valgrind est un outil libre qui facilite le deboguage de programme en contrôlant la validité
des accès à la mémoire. Ainsi il permet de déceler les déférencements de pointeurs, les lectures
ou écritures à des zones mémoires invalides (non allouées, protégées, ...), les fuites de mémoire
(oublie d'un \textit{free()}, ...)... Il permet également d'avoir un aperçu sur la consommation
mémoire de notre programme en affichant la taille de toutes les zones mémoire allouées. Nous
lançons donc notre programme sous valgrind avec des images de différentes tailles.

\begin{small}
\begin{verbatim}
(clem1@clem1:~/perso/svn/pnmascii)$ valgrind ./asciirt -o foo tests/p5.pgm 
(...)
DEBUG: pnmload: witdh: 119 - heigh: 238 - maxcol: 255
debug> mallocage de 953o

==6082== 
==6082== ERROR SUMMARY: 0 errors from 0 contexts 
==6082== malloc/free: in use at exit: 0 bytes in 0 blocks.
==6082== malloc/free: 4 allocs, 4 frees, 1,696 bytes allocated.
==6082== All heap blocks were freed -- no leaks are possible.
\end{verbatim}
\begin{verbatim}
(clem1@clem1:~/perso/svn/pnmascii)$ valgrind ./asciirt -o foo tests/paumier.ppm 
(...)
DEBUG: pnmload: witdh: 222 - heigh: 343 - maxcol: 255
debug> mallocage de 1777o

==6083== 
==6083== ERROR SUMMARY: 0 errors from 0 contexts
==6083== malloc/free: in use at exit: 0 bytes in 0 blocks.
==6083== malloc/free: 4 allocs, 4 frees, 2,520 bytes allocated.
==6083== All heap blocks were freed -- no leaks are possible.
\end{verbatim}
\end{small}

L'exécution de notre programme sous valgrind nous montre que nous n'avons pas de fuite mémoire
(\textit{no leaks}) et que nous avons alloué au total seulement 2 kilo-octets avec 4 appels à
\textit{malloc()}.

\section{Performances}

Pour avoir un aperçu des performances de notre programme, nous pouvons utiliser un outil de
profilage qui permet de détailler combien de temps processeur dure chaque fonction et combien
de fois elle a été appelée. Cela permet de déceler les points "noirs" de notre programme
et les fonctions à eventuellement optimiser. Dans le monde du libre, l'outil de profilage
le plus connu et le plus simple à manipuler est gprof (avec g pour GNU). Valgrind possède
également un outil similaire appelé callgrind. On recomplile donc notre programme avec gcc
et l'option -pg puis on analyse les gmon.out (générés après exécution) avec gprof, on obtient
alors les statistiques suivantes:

% TODO STAT!


%\end{section}

\section{Conclusion}

Ce projet, très intéressant, nous a permis de découvrir les différentes facettes de la programmation
C et la réalisation d'un vrai projet en équipe (organisation). Le projet sera publié sur googlecode et
maintenu (par Clément) si des personnes sont intéressées (ajout de fonctionnalité, support des couleurs)
même s'il existe des librairies faciles d'utilisation qui permettent de convertir des images en ascii
comme la libcaca de Sam Hocevar.

\newpage

\begin{figure}
\begin{center}
\begin{scriptsize}
\begin{verbatim}
                             ."^^_                              
                         .R@@gp@@wk@w/                          
                       "@@@u"      >B@mg.                       
                      q$mt            !$mu                      
                    "$mr................q$@                     
                   t$$i::::-::::::::::--:y$$:                   
                  >$$U````````````````````k$$.                  
                 .$$g""""""""""""""""""""""@$m                  
                 @$$>+>Y33dx%>^+^^^^^^^^+^^{$$a                 
                1$$q>/du%|/Uuu(>>>>>>>>>>>>>m$$.                
                $$$AXj2gwkgkpkaAtttt]1//i]ttg$$g                
               >$$$Jraqpi: "r@$mC\XaQn%LojQ1j$$$                
               q$$$yapq+:    t$$pMg?0kgqk!ykr$$$O               
               $$$$kp@>"`:    {$@@@qB33rqwqg@$$$p               
              :$$$$k@/^_:..  .~@@mq>"`   >ww$$$$$               
              t$$$mkp+"~.... .`{q0>"~-:   _q$$$$$               
              R$$$@qE"_-.:..:EXTa[];....  .>$$$$$"              
              E$$$m@u__-::::h$$7E$>i..... ~>$$$$$>              
              w$$$$$K__~::::n$$$0$$@::::::_>$$$$$c              
              @$$$$$a_`~;:::I@$$a$$w:::::~">$$$$$M              
              $$$$$$p"``~;-->Uggw!k]~-:;~_<]$$$$$@              
              $$$$$$$>_`=~~~`>4Lm[>"__`__">@$$$$$$              
             >$$$$$$$B"`__`">>+"_"^"<~~~_t@$$$$$$$              
             y$$$$$$$${"_">>+_:.    ">>{q$$$$$$$$$/             
             @$$$$$$$$$1^^>>+<"_.    >]1@$$$$$$$$$@             
            zw$$$$$$$$g]]T{+^<""_~. ->^"_r$$$$$$$$gI            
            Mw$$$$$$$r`<>]{{<<""""`->>~.  /$$$$$$$w0.           
           &d@$$$$$$a  :`">1i<""""">t"     /$$$$$$@Xj           
          kBT@$$$$$q     .~+}]"""<>t+.      r$$$$$@1ur          
         kk>R$$$$$$.       :^]t_<>t>~        @$$$$$3>rr         
        yk>iw$$$$$t         ~+>>>>>".        _$$$$$@|>RB`       
      >kZ>{$$$$$$@           `^>>>":          0$$$$$$QttkW      
     Z0>>a$$$$$$$^           .~""_;           ~$$$$$$$qt>Mk     
    3u>t@$$$$$$$@             .;~:.            g$$$$$$$$i>BB    
   {e>Y$$$$$$$$$X              ..              >$$$$$$$$$r>Ea   
  _B>9$$$$m$$$$$`                              ~$$$$$@$$$$k>a>  
  0]M$$$Bog$$$$$~                              =g$$$$q[am$$w>k  
 zk0$$rn> o$$$$B~..............................`U$$$$g  %3@$wB! 
 jrmBC^   {$$$${~..............................`>$$$$B    !r@gj 
 +@3t     >$$$$>~..............................__$$$$Z     :Ya  
          .$$$$"`::::::::::::::::::::::::::::::__$$$$>          
           w$$$__::::::::::::::::::::::::::::::__$$$g           
           q@$$"_~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~""$$@g           
           Tq$$"_~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~""$$ka           
            ga@>"`````````````````````````````_""@rg-           
            0Bat"______________________________"^Rug            
             kci"""__________________________""">Ig<            
             rk{""""""""""""""""""""""""""""""""iyg             
              &2""<<<<""<"""""""""""""""<""<^<""{g              
              "ktt]]}i1zt>+^<""""""<^+>>}Tz}]]ttM/              
             >>>>^">t]}z1|z>>+^<"<^>>]111i]t>"_>>>>~            
           ">>"     .:>t}z//]>>^^+>t//1i]t_       >>>           
          ">>.       .:>t]i//i>>>>]//z]t>.         ^>>          
          >>`::......::->>]i/{}>>]//T]t><:......::::>>>         
         >>>~~~~~~;~~~~~>>t]T{{]]|{/}t>>_~~~~~~~~~~~_>>         
        :>>+_____`_````_^>>ti/Y/zY{T]>>^<____`______">>".       
       ;">>+"""""""""""^^^>>]/!Y/X{it>+^^"""""""""""^>>>"~.     
      ~">>>>+^^<<<<<^<++>>>>]/LsJI{it>>>++^<<<<<<^^+>>tt>"~.    
     .=">tt>>>>>>>>>>>>>>>>t}sa&aaRit>>>>>>>>>>>>>>>>ttt><_:    
     .~_">>>>>>>ttt]]]}iizz\1IIII[c{11Tziii}]]]ttttttt>>^"~.    
      .:~=__"""<^^>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>^^<"""_`~:.     
           ....:::-;~~~~~~~```````````=~~~~~~;-::::...
\end{verbatim}
\end{scriptsize}
\end{center}
\caption{LINUX RULAIZE \#@!!\#@\#@!}
\end{figure}

\end{document}
